﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
using System.Diagnostics;
using Faml.Frontend;
using System.Reflection;
using System.Collections.Specialized;


namespace Faml.Optimization
{
    public class CommonExpressionEliminator
    {
        private FamlExpression expression;

        public CommonExpressionEliminator(FamlExpression expression)
        {
            this.expression = expression;
        }

        public bool Optimize()
        {
            BuildClasses();
            return true;
        }

        /// <summary>
        /// Gets an execution-ordered list of extracted expressions.
        /// </summary>
        public LinkedList<FamlExpressionContainer> OrderedExpressions
        {
            get
            {
                if (expression == null || classes == null)
                    throw new ApplicationException("Call Optimize() first");

                LinkedList<FamlExpressionContainer> expressions = new LinkedList<FamlExpressionContainer>();
                if (classes != null && classes.Count > 0)
                    foreach (FamlExpressionClass @class in classes)
                    {
                        if (@class.FamlReference != null)
                            expressions.AddLast(@class.FamlReference.ReferencedContainer);
                    }
                else
                {
                    expressions.AddLast(new FamlExpressionContainer(expression));
                }

                return expressions;
            }
        }

        List<FamlExpressionClass> classes;

        private void BuildClasses()
        {
            Dictionary<int, FamlExpressionClass> taxonomy = new Dictionary<int, FamlExpressionClass>();
            BuildClasses(taxonomy, expression);

            classes = new List<FamlExpressionClass>(taxonomy.Values);
            PrintClasses("Classification result (stage 0 / base classification): ", classes);

            RemoveSimpleClasses(classes, false);
            PrintClasses("Classification result (stage 1 / simple classes removed): ", classes);

            RebuildClasses(classes);
            PrintClasses("Classification result (stage 2 / rebuilt): ", classes);
                        

            RemoveSimpleClasses(classes, true);
            RemoveParameterizedClasses(classes); 
            PrintClasses("Classification result (stage 3 / simple & parameterized classes removed): ", classes);

            AddExtraClasses(expression);
            PrintClasses("Classification result (stage 4 / extra classed added): ", classes);

            if (classes.Count > 0)
            {
                // Adding a class for the entire expression
                FamlExpressionClass @class = new FamlExpressionClass(expression);
                classes.Add(@class);
                
                BuildDependencyOrder(expression);

                ApplyClasses();
            }
        }

        private void AddExtraClasses(FamlExpression exp)
        {
            List<FamlExpressionClass> processed = new List<FamlExpressionClass>(classes.Count);
            AddExtraClasses(exp, processed);
        }

        private void AddExtraClasses(FamlExpression exp, List<FamlExpressionClass> processed)
        {
            if (exp.NodeType == FamlExpressionType.FunctionCall)
            {
                FamlFunctionCallExpression fce = (FamlFunctionCallExpression)exp;

                if (string.Compare(fce.Function, "unfold", true) == 0 && fce.Metadata.IsIndependent)
                {
                    MethodInfo unfold = fce.Operation.Method;
                    ParameterInfo[] unfoldParams = unfold.GetParameters();
                    for (int i = 0; i < unfoldParams.Length; i++)
                    {
                        if (unfoldParams[i].ParameterType == typeof(int))                            
                        {
                            bool cond = fce.Arguments[i].NodeType != FamlExpressionType.Constant;

                            if (cond)
                            {
                                FamlExpressionClass unfoldArgClass = fce.Arguments[i].Class;
                                if (unfoldArgClass == null)
                                {
                                    unfoldArgClass = new FamlExpressionClass(fce.Arguments[i]);
                                    classes.Add(unfoldArgClass);
                                }
                                unfoldArgClass.NonRemovableClass = true;
                            }
                        }
                    }


                    FamlExpressionClass unfoldClass = fce.Class;
                    if (unfoldClass == null)
                    {
                        unfoldClass = new FamlExpressionClass(fce);
                        unfoldClass.NonRemovableClass = true;
                        classes.Add(unfoldClass);
                    }
                    unfoldClass.NonRemovableClass = true;
                }
                else if (string.Compare(fce.Function, "eval", true) == 0)
                {
                    if (!fce.Metadata.IsIndependent)
                    {
                        throw new Exception("eval() cannot be dependant");
                    }

                    MethodInfo eval = fce.Operation.Method;
                    
                    FamlExpressionClass evalClass = fce.Class;
                    if (evalClass == null)
                    {
                        evalClass = new FamlExpressionClass(fce);
                        classes.Add(evalClass);
                    }
                    evalClass.NonRemovableClass = true;
                }
            }

            if (exp.Class == null || !processed.Contains(exp.Class))
            {
                foreach (FamlExpression item in exp.Children)
                {
                    AddExtraClasses(item, processed);
                }
                if (exp.Class != null)
                    processed.Add(exp.Class);
            }
        }
        

        private void ApplyClasses()
        {   
            /***************************************************************/
            // Walking on the expression tree and change sub-expressions
            ApplyClasses(ref expression);
        }

        private bool ApplyClasses(ref FamlExpression expression)
        {
            FamlExpression oldExpr = expression;

            // 1. Looking whether this expression belongs to a class or not?            
            FamlExpressionClass @class = expression.Class;

            // 2. We have an expression of this class. 
            // Now we have to find whether a delegate already exists for this class or do not.
            if (@class == null || @class.FamlReference == null)
            {
                bool b = false;
                int i = 0;
                switch (expression.NodeType)
                {
                    case FamlExpressionType.Dictionary:

                        FamlDictionaryExpression fde = (FamlDictionaryExpression)expression;
                        string[] keys = fde.GetKeys();
                        OrderedDictionary dict = new OrderedDictionary(keys.Length);

                        b = false;
                        FamlExpression exp;
                        for (i = 0; i < keys.Length; i++)
                        {
                            exp = fde.GetField(keys[i]);
                            b = ApplyClasses(ref exp) || b;
                            dict.Add(keys[i], exp);
                        }

                        if (b)
                        {
                            expression = new FamlDictionaryExpression(dict);
                        }
                        break;


                    case FamlExpressionType.ConditionalExpression:

                        FamlConditionalExpression fcnde = (FamlConditionalExpression)expression;
                        FamlExpression cond = fcnde.Condition, trueBr = fcnde.TrueBranch, falseBr = fcnde.FalseBranch;

                        b = ApplyClasses(ref cond);
                        b = ApplyClasses(ref trueBr) || b;
                        b = ApplyClasses(ref falseBr) || b;

                        if (b)
                        {
                            expression = new FamlConditionalExpression(cond, trueBr, falseBr);
                        }
                        break;


                    case FamlExpressionType.FieldAccess:

                        FamlFieldExpression me = (FamlFieldExpression)expression;

                        FamlExpression expr = me.Target;
                        if (ApplyClasses(ref expr))
                        {
                            expression = new FamlFieldExpression(expr, me.Field);
                        }
                        break;


                    case FamlExpressionType.UnaryExpression:

                        FamlUnaryExpression ue = (FamlUnaryExpression)expression;

                        FamlExpression operand = ue.Target;
                        if (ApplyClasses(ref operand))
                        {
                            expression = new FamlUnaryExpression(ue.Operator, operand);
                        }
                        break;


                    case FamlExpressionType.BinaryExpression:

                        FamlBinaryExpression be = (FamlBinaryExpression)expression;

                        b = false;
                        FamlExpression operandLeft = be.Left;
                        FamlExpression operandRight = be.Right;

                        b = ApplyClasses(ref operandLeft);
                        b = ApplyClasses(ref operandRight) || b;

                        if (b)
                        {
                            expression = new FamlBinaryExpression(operandLeft, operandRight, be.Operator);
                        }
                        break;


                    case FamlExpressionType.NewArray:
                        FamlInlineArrayExpression nae = (FamlInlineArrayExpression)expression;

                        if (nae.Items.Count != 0)
                        {
                            FamlExpression[] newargs = new FamlExpression[nae.Items.Count];
                            i = 0;
                            b = false;
                            foreach (FamlExpression arg in nae.Items)
                            {
                                newargs[i] = arg;
                                b = ApplyClasses(ref newargs[i]) || b;
                                i++;
                            }

                            if (b)
                            {
                                expression = new FamlInlineArrayExpression(newargs);
                            }
                        }
                        break;


                    case FamlExpressionType.Lambda:

                        FamlLambdaExpression lexp = (FamlLambdaExpression)expression;

                        FamlUnaryExpression body = lexp.Body as FamlUnaryExpression;
                        FamlExpression realBody = body.Target;
                        if (ApplyClasses(ref realBody))
                        {
                            FamlLambdaParameter[] newparams = lexp.Parameters.ToArray<FamlLambdaParameter>();
                            expression = new FamlLambdaExpression(realBody, newparams);
                        }
                        break;

                    
                    case FamlExpressionType.FunctionCall:

                        FamlFunctionCallExpression fce = (FamlFunctionCallExpression)expression;

                        FamlExpression[] fcenewargs = new FamlExpression[fce.Arguments.Count];
                        i = 0;
                        b = false;
                        foreach (FamlExpression arg in fce.Arguments)
                        {
                            fcenewargs[i] = arg;
                            b = ApplyClasses(ref fcenewargs[i]) || b;
                            i++;
                        }

                        if (b)
                        {
                            expression = new FamlFunctionCallExpression(fce.Operation, fcenewargs);
                        }
                        break;
                }

                if (@class != null)
                {
                    expression = @class.FamlReference = new FamlReferenceExpression(expression);
                }
            }
            else
            {
                expression = @class.FamlReference;
            }

            return expression != oldExpr;
        }
        


        public delegate T GetValueDelegate<T>(int id);

        private void RebuildClasses(List<FamlExpressionClass> taxonomy)
        {
            List<FamlExpressionClass> toAdd = new List<FamlExpressionClass>();

            foreach (var c in taxonomy)
            {
                CheckUniform(c, toAdd);                
            }

            foreach (FamlExpressionClass ec in toAdd)
            {
                taxonomy.Add(ec);
            }
        }

        private void CheckUniform(FamlExpressionClass c, List<FamlExpressionClass> list)
        {
            FamlExpression e1, e2;
            IList<FamlExpression> nodes = c.Expressions;
            List<FamlExpression> toRemove = new List<FamlExpression>();

            e1 = nodes[0];
            for (int j = 1; j < nodes.Count; j++)
            {
                e2 = nodes[j];

                if (!Compare(e1, e2))
                {
                    toRemove.Add(e2);
                }
            }

            if (toRemove.Count != 0)
            {
                FamlExpressionClass newclass = null; 
                foreach (var item in toRemove)
                {
                    if (newclass == null)
                        newclass = new FamlExpressionClass(item);
                    else
                        newclass.Add(item);
                    nodes.Remove(item);
                }
                
                list.Add(newclass);
                CheckUniform(newclass, list);
            }
        }

        private bool Compare(FamlExpression e1, FamlExpression e2)
        {
            if (e1 == null || e2 == null)
                return e1 == e2;
            if (e1.NodeType != e2.NodeType ||
                e1.Type != e2.Type ||
                e1.Metadata.Height != e1.Metadata.Height)
                return false;
          
            switch (e1.NodeType)
            {
                case FamlExpressionType.FieldAccess:

                    FamlFieldExpression me1 = (FamlFieldExpression)e1;
                    FamlFieldExpression me2 = (FamlFieldExpression)e2;

                    if (me1.Field != me2.Field ||
                        !Compare(me1.Target, me2.Target))
                        return false;

                    return true;

                    
                case FamlExpressionType.UnaryExpression:

                    FamlUnaryExpression ue1 = (FamlUnaryExpression)e1;
                    FamlUnaryExpression ue2 = (FamlUnaryExpression)e2;

                    if (ue1.Operator != ue2.Operator ||
                       !Compare(ue1.Target, ue2.Target))
                        return false;

                    return true;


                case FamlExpressionType.BinaryExpression:

                    FamlBinaryExpression be1 = (FamlBinaryExpression)e1;
                    FamlBinaryExpression be2 = (FamlBinaryExpression)e2;

                    if (be1.Operator != be2.Operator ||
                       !Compare(be1.Left, be2.Left) ||
                        !Compare(be1.Right, be2.Right))
                        return false;

                    return true;


                case FamlExpressionType.Constant:

                    FamlConstant c1 = (FamlConstant)e1;
                    FamlConstant c2 = (FamlConstant)e2;
                    return c1.Value.Equals(c2.Value);


                case FamlExpressionType.NewArray:

                    FamlInlineArrayExpression nae1 = (FamlInlineArrayExpression)e1;
                    FamlInlineArrayExpression nae2 = (FamlInlineArrayExpression)e2;

                    if (nae1.Items.Count != nae2.Items.Count)
                        return false;

                    for (int i = 0; i < nae1.Items.Count; i++)
                    {
                        if (!Compare(nae1.Items[i], nae2.Items[i]))
                            return false;
                    }
                    return true;

                    
                case FamlExpressionType.DefParameter:
                    
                    throw new ApplicationException("Def parameter found; shall it be expanded up to now?");


                case FamlExpressionType.LambdaParameter:

                    FamlLambdaParameterExpression p1 = (FamlLambdaParameterExpression)e1;
                    FamlLambdaParameterExpression p2 = (FamlLambdaParameterExpression)e2;
                    return p1.Type == p2.Type;


                case FamlExpressionType.Lambda:

                    FamlLambdaExpression lexp1 = (FamlLambdaExpression)e1;
                    FamlLambdaExpression lexp2 = (FamlLambdaExpression)e2;

                    bool equal = lexp2.Parameters.Count == lexp1.Parameters.Count &&
                        Compare(lexp1.Body, lexp2.Body);
                    if (!equal) return false;

                    for (int i = 0; i < lexp1.Parameters.Count; i++)
                    {
                        if (!Compare(lexp1.Parameters[i], lexp2.Parameters[i]))
                            return false;
                    }
                    return true;


                case FamlExpressionType.FunctionCall:

                    FamlFunctionCallExpression mce1 = (FamlFunctionCallExpression)e1;
                    FamlFunctionCallExpression mce2 = (FamlFunctionCallExpression)e2;
                    if (mce1.Operation != mce2.Operation
                        || mce1.Arguments.Count != mce2.Arguments.Count )
                        return false;

                    for (int i = 0; i < mce1.Arguments.Count; i++)
                    {
                        if (!Compare(mce1.Arguments[i], mce2.Arguments[i]))
                            return false;
                    }
                    return true;

                case FamlExpressionType.ConditionalExpression:
                    FamlConditionalExpression fce1 = (FamlConditionalExpression)e1;
                    FamlConditionalExpression fce2 = (FamlConditionalExpression)e2;
                    return Compare(fce1.Condition, fce2.Condition) &&
                        Compare(fce1.TrueBranch, fce2.TrueBranch) &&
                        Compare(fce1.FalseBranch, fce2.FalseBranch);

                case FamlExpressionType.Dictionary:
                    FamlDictionaryExpression fde1 = (FamlDictionaryExpression)e1;
                    FamlDictionaryExpression fde2 = (FamlDictionaryExpression)e2;
                    string[] keys1 = fde1.GetKeys();
                    string[] keys2 = fde2.GetKeys();

                    if (keys1.Length != keys2.Length) return false;
                    for (int i = 0; i < keys1.Length; i++)
                    {
                        if (keys2[i] != keys1[i]) return false;
                        if (!Compare(fde1.GetField(keys1[i]), fde2.GetField(keys1[i])))
                            return false;
                    }
                    return true;

                /*case FamlExpressionType.ExpressionClass:
                    break;
                case FamlExpressionType.ExpressionReference:
                    break;*/


                default:
                    throw new ApplicationException("Unexpected node type found: " + e1.NodeType);
            }
        }

        private bool Compare(FamlLambdaParameter p1, FamlLambdaParameter p2)
        {
            return p1.Type == p2.Type; 
        }

        private int RemoveSimpleClasses(List<FamlExpressionClass> classes, bool removeByType)
        {
            int removed = 0;
            for (int i = classes.Count; --i >= 0; )
            {
                FamlExpressionClass ec = classes[i];
                if (ec.Power < 2)
                {
                    ec.RemoveClass();
                    classes.RemoveAt(i);
                    removed++;
                }
                else if (removeByType)
                {
                    if (ec.ExpressionsType == FamlExpressionType.UnaryExpression &&
                        ((FamlUnaryExpression)ec.Expression).Operator == UnaryOperations.Quote)
                    {
                        ec.RemoveClass();
                        classes.RemoveAt(i);
                        removed++;
                    }
                    else if (ec.Height == 1)
                    {
                        FamlExpressionType type = ec.ExpressionsType;
                        bool stay = type == FamlExpressionType.FunctionCall ||
                            type == FamlExpressionType.NewArray;
                            //type == FamlExpressionType.New ||
                            //type == FamlExpressionType.NewArrayBounds ||
                            //type == FamlExpressionType.NewArrayInit;
                        if (!stay)
                        {
                            ec.RemoveClass();
                            classes.RemoveAt(i);
                            removed++;
                        }
                    }
                }
            }

            Debug.WriteLine(string.Format("{0} simple classes found. They are removed.", removed));
            return removed;
        }

        private int RemoveParameterizedClasses(List<FamlExpressionClass> classes)
        {
            int removed = 0;
            for (int i = classes.Count; --i >= 0; )
            {
                if (!classes[i].IsIndependent)
                {
                    classes[i].RemoveClass();
                    classes.RemoveAt(i);
                    removed++;
                }
            }

            Debug.WriteLine(string.Format("{0} parameterized classes found. They are removed.", removed));
            return removed;
        }

        private void BuildDependencyOrder(FamlExpression expression)
        {
            processedClass = new List<FamlExpressionClass>();
            IEnumerable<FamlExpressionClass> start = GetDescendants(expression); // builds processedClass

            // 1. Selecting Entry nodes
            LinkedList<FamlExpressionClass> queue = new LinkedList<FamlExpressionClass>();
            for(int i = 0; i < processedClass.Count; i++)
            {
                FamlExpressionClass ec = processedClass[i];

                if (!ec.IsDependantClass)
                    queue.AddLast(ec);                
            }

            // 2. Reduction of entry nodes
            int reduced = 0;
            LinkedListNode<FamlExpressionClass> node = queue.First;
            while (node != null)
            {
                FamlExpressionClass entry = node.Value;
                if (entry.HasDependingOnMe && entry.DependingOnMe.Count == 1 && !entry.NonRemovableClass)
                {
                    FamlExpressionClass depc = entry.DependingOnMe[0];
                    entry.RemoveClass();

                    if (!depc.IsDependantClass)
                        queue.AddLast(depc);

                    reduced++;

                    LinkedListNode<FamlExpressionClass> rn = node;
                    node = node.Next;
                    queue.Remove(rn);
                }
                else
                {
                    node = node.Next;
                }
            }

            // 3. TODO: Reduction of middle-nodes with single output edge.
            Debug.WriteLineIf(reduced > 0, string.Format("{0} classes removed since they have single dependant class", reduced));

            // 4. Building class evaluation order
            FamlExpressionClass @class;
            classes.Clear();
            int index = 0;          
            
            while (queue.Count != 0)
            {
                node = queue.First;

                do
                {
                    @class = node.Value;

                    if (@class.HasDependingOnMe)
                    {
                        for (int i = 0; i < @class.DependingOnMe.Count; i++)
                        {
                            FamlExpressionClass adjClass = @class.DependingOnMe[i];

                            adjClass.RemoveOneInEdge();
                            if (adjClass.EvaluationIndex == -1 /* white */ && !adjClass.IsDependantClass)
                            {
                                queue.AddLast(adjClass);
                                adjClass.EvaluationIndex = -2; /* gray */
                            }
                        }
                    }

                    if (@class.EvaluationIndex < 0)
                    {
                        @class.EvaluationIndex = index++; /* black */
                        classes.Add(@class);
                        LinkedListNode<FamlExpressionClass> remove = node;
                        node = node.Next;
                        queue.Remove(remove);
                    }
                    else
                    {
                        node = node.Next;
                    }
                } while (node != null);
            }
        }

        private List<FamlExpressionClass> processedClass;

        private IEnumerable<FamlExpressionClass> GetDescendants(FamlExpression expression)
        {
            List<FamlExpressionClass> desc = null;
            FamlExpressionClass @class = expression.Class;

            if (@class != null && processedClass.Contains(@class))
                return new FamlExpressionClass[] { @class };

            foreach (FamlExpression child in expression.Children)
            {
                IEnumerable<FamlExpressionClass> cd = GetDescendants(child);
                if (cd != null)
                {
                    if (desc == null)
                        desc = new List<FamlExpressionClass>();
                    desc.AddRange(cd);
                }
            }

            if (@class == null)
                return desc;

            if (desc != null)
            {
                foreach (FamlExpressionClass dep in desc)
                {
                    dep.AddClassDependingOnMe(@class);
                }
            }

            processedClass.Add(@class);
            return new FamlExpressionClass[] { @class };
        }

        private void BuildClasses(Dictionary<int, FamlExpressionClass> taxonomy, FamlExpression expression)
        {
            if (expression.NodeType == FamlExpressionType.LambdaParameter ||
                expression.NodeType == FamlExpressionType.Constant)
                return;

            foreach (FamlExpression child in expression.Children)
            {
                BuildClasses(taxonomy, child);
            }

            if (expression.NodeType == FamlExpressionType.UnaryExpression &&
                ((FamlUnaryExpression)expression).Operator == UnaryOperations.Quote)
                return;
            if (expression.NodeType == FamlExpressionType.Constant)
                return;
            if (expression.NodeType == FamlExpressionType.Lambda)
                return;

            FamlExpressionExtension ext = expression.Metadata;
                        
            FamlExpressionClass exclass;
            if (!taxonomy.TryGetValue(ext.Hash, out exclass))
            {
                exclass = new FamlExpressionClass(expression);
                taxonomy.Add(ext.Hash, exclass);
            }
            else
            {
                exclass.Add(expression);
            }
        }

        private void PrintClasses(string message, List<FamlExpressionClass> t)
        {
            Debug.WriteLine(message + " (" + t.Count + " classes)");
            foreach (var c in t)
            {
                System.Diagnostics.Debug.WriteLine(string.Format("{0}", c));
            }
        }
    }   
}
